import java.util.LinkedList;

/*
 * @lc app=leetcode.cn id=103 lang=java
 *
 * [103] 二叉树的锯齿形层次遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        //主要是画个图整明白了即可，用两个stack
        //java里面是stack
        //两个栈吧，一个从左到右压入，一个从右到左压入
//        我又想了一下，其实用一个双向链表，也可以说是双向栈，应该也能解决，就是很麻烦。
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        List<List<Integer>> ans = new ArrayList<>();
        if(root == null) return ans;
        stack1.add(root);//先把根节点放进去
        while(!(stack1.isEmpty() && stack2.isEmpty()) ){//两个栈都空才停止循环
            List<Integer> temp = new ArrayList<>();
            if(!stack1.empty()){
                while (!stack1.isEmpty()){
                    //此时需要将值抛出，并从左往右访问节点压入stack2
                    TreeNode t = stack1.pop();
                    temp.add(t.val);
                    if(t.left!=null){
                        stack2.push(t.left);
                    }
                    if(t.right!=null){
                        stack2.push(t.right);
                    }
                }

            }else if(!stack2.empty()) {
                while (!stack2.isEmpty()){
                    //此时需要将值抛出，并从右往左访问节点压入stack1
                    TreeNode t = stack2.pop();
                    temp.add(t.val);
                    if(t.right!=null){
                        stack1.push(t.right);
                    }
                    if(t.left!=null){
                        stack1.push(t.left);
                    }
                }

            }
            ans.add(temp);
        }
        return ans;
    }
}
// @lc code=end

